package com.example.coinsgame;

/**
 * 四种硬币 1元3元4元5元  n元钱最少几个硬币
 * 使用动态规划法
 */
public class CoinsGameMain {


    public static void main(String[] args) {
        int[] is = {1,3,4,5};
        fun(7,is);
    }

    public static void fun(int k, int[] is){
        int[] i1 = new int[99];
        for (int l=0;l<k+1;l++){
            if(l==0){
                i1[0] = 0;
            } else {
                int[] i2 = new int[4];
                for (int j=0;j<is.length;j++){
                    int ks = l - is[j];
                    if(ks >=0){
                        i2[j] = i1[ks]+1;
                    }
                }
                i1[l] = min(i2);
            }
            if (l==k){
                System.out.println((k)+":"+i1[l]);
            }
        }
    }

    private static int min(int[] i1){
        if (i1.length==0) return 0;
        int m = i1[0];
        for (int i=0;i<i1.length;i++){
            if(i1[i]!=0&&i1[i]<m){
                m=i1[i];
            }
        }
        return m;
    }

}
